/** `95` 不同的二叉搜索树 II

 */

use std::rc::Rc;
use std::cell::RefCell;
use crate::solution::Solution;
use crate::tree_node::TreeNode;

impl Solution {
    pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        fn dfs(left: i32, right: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
            if left > right || right < left {
                vec![None]
            } else if left == right {
                vec![Some(Rc::new(RefCell::new(TreeNode::new(left))))]
            } else {
                let mut ans = vec![];
                for i in left..=right {
                    let tl = dfs(left, i - 1);
                    let tr = dfs(i + 1, right);
                    for x in tl {
                        for y in tr.iter() {
                            ans.push(Some(Rc::new(RefCell::new(TreeNode {
                                val: i,
                                left: x.clone(),
                                right: y.clone(),
                            }))))
                        }
                    }
                }
                ans
            }
        }
        dfs(1, n)
    }
}

